Grokking Tree Coding Patterns for Interviews
Rate this course
Ask Author
Contribute
Back to course home

0% completed

Vote For New Content
Introduction
Course Overview
Basics of Tree
Introduction to Tree
Types of Tree
BST Traversal Techniques
BST Operations
Level Order Traversal Pattern (easy)
Introduction to Level Order Traversal Pattern
Reverse Level Order Traversal (easy)
Solution: Reverse Level Order Traversal
Find Largest Value in Each Tree Row (medium)
Solution: Find Largest Value in Each Tree Row
Maximum Width of Binary Tree (medium)
Solution: Maximum Width of Binary Tree
Maximum Level Sum of a Binary Tree (medium)
Solution: Maximum Level Sum of a Binary Tree
Zigzag Traversal (medium)
Solution: Zigzag Traversal
Even Odd Tree (medium)
Solution: Even Odd Tree
N-ary Tree Level Order Traversal (hard)
Solution: N-ary Tree Level Order Traversal
Tree Depth Pattern (easy)
Introduction to Tree Depth Pattern
Maximum Depth (or Height) of Binary Tree (easy)
Solution: Maximum Depth (or Height) of Binary Tree
Minimum Depth of a Binary Tree (easy)
Solution: Minimum Depth of a Binary Tree
Balanced Binary Tree (easy)
Solution: Balanced Binary Tree
Tree Diameter (easy)
Solution: Tree Diameter
Maximum Depth of N-ary Tree (easy)
Solution: Maximum Depth of N-ary Tree
Find maximum depth of subtree (medium)
Solution: Find maximum depth of subtree
Introduction to Root to Leaf Path Pattern
Binary Tree Paths (easy)
Solution: Binary Tree Paths
Sum of Root To Leaf Binary Numbers (easy)
Solution: Sum of Root To Leaf Binary Numbers
Insufficient Nodes in Root to Leaf Paths (medium)
Solution: Insufficient Nodes in Root to Leaf Paths
Smallest String Starting From Leaf (medium)
Solution: Smallest String Starting From Leaf
Pseudo-Palindromic Paths in a Binary Tree (medium)
Solution: Pseudo-Palindromic Paths in a Binary Tree
All Paths for a Sum (medium)
Solution: All Paths for a Sum
Sum of Path Numbers (medium)
Solution: Sum of Path Numbers
Path With Given Sequence (medium)
Solution: Path With Given Sequence
Count Paths for a Sum (medium)
Solution: Count Paths for a Sum
Introduction to Leaf Processing Pattern
Sum of Left Leaves (easy)
Solution: Sum of Left Leaves
Leaf-Similar Trees (easy)
Solution: Leaf-Similar Trees
Check if all leaves are at same level (medium)
Solution: Check if all leaves are at same level
Delete Leaves With a Given Value (medium)
Solution: Delete Leaves With a Given Value
Deepest Leaves Sum (medium)
Solution: Deepest Leaves Sum
Introduction to Tree View Pattern
Right View of a Binary Tree (medium)
Solution: Right View of a Binary Tree
Top View Of the Binary Tree (medium)
Solution: Top View Of the Binary Tree
Bottom View Of the Binary Tree (medium)
Solution: Bottom View Of the Binary Tree
Boundary of Binary Tree (medium)
Solution: Boundary of Binary Tree
Introduction to Comparison of Two Trees Pattern
Symmetric Tree (easy)
Solution: Symmetric Tree
Mirror Image Trees (medium)
Solution: Mirror Image Trees
Subtree of Another Tree (easy)
Solution: Subtree of Another Tree
Isomorphic Trees (medium)
Solution: Isomorphic Trees
Introduction to Serialize and Deserialize Tree Pattern
Serialize and Deserialize BST (medium)
Solution: Serialize and Deserialize BST
Verify Preorder Serialization of a Binary Tree (medium)
Solution: Verify Preorder Serialization of a Binary Tree
Create Binary Tree From Descriptions (medium)
Solution: Create Binary Tree From Descriptions
Serialize and Deserialize N-ary Tree (hard)
Solution: Serialize and Deserialize N-ary Tree
Solution: Find maximum depth of subtree

Problem Statement

Given the root node of a binary tree and an integer val, find the maximum depth of the subtree that starts from the node with the value equal to val. If the node with value val doesn't exist in the tree, return 0.

The depth of a node is defined as the number of edges on the longest path from the node to a leaf.

Examples

Example 1

  • Input: root = [3, 5, 4, 2, null, 1, null, 6], val = 5
Image
  • Expected Output: 3
  • Explanation: The subtree starting from the node with value 5 has nodes 5, 2, and 6. The maximum depth of this subtree is 3.

Example 2

  • Input: root = [1, 2, 3, 4, null, null, 5, 6], val = 3
Image
  • Expected Output: 2
  • Explanation: The subtree starting from the node with value 3 has nodes 3 and 5. The maximum depth of this subtree is 2.

Example 3

  • Input: root = [7, 3, 9, 1, 6, null, 8, null, null, null, 2], val = 3
Image
  • Expected Output: 3
  • Explanation: The subtree starting from the node with value 3 has nodes 3, 6, and 2. The maximum depth of this subtree is 3.

Solution

To solve this problem, we need to locate the node in the binary tree that has the value equal to val. Once we find this node, the task is to determine the depth of the subtree rooted at this node. Depth in this context means the number of edges on the longest path from the node to any of its leaf nodes.

We will utilize Depth-First Search (DFS) to explore all possible paths from the root node until we find the desired node. After locating the node, we continue the DFS to measure the depth of the subtree. This approach is efficient for this problem because DFS will allow us to traverse deep into the tree, ensuring we account for all possible depths before concluding.

Step-by-Step Algorithm

Part 1: Finding the Node with Value val

  1. Start at the root node:

    • Begin the search from the root node of the tree.
  2. Check if the tree is empty:

    • If the root is null, return 0 because the tree is empty.
  3. Check if the current node's value matches val:

    • Compare the value of the current node (root.val) with the target value val.
    • If they match, proceed to the next part to calculate the depth of the subtree.
  4. Search in the left subtree:

    • If the current node's value doesn't match val, recursively search in the left subtree by calling the method on root.left.
  5. Search in the right subtree:

    • If the node is not found in the left subtree, recursively search in the right subtree by calling the method on root.right.

Part 2: Finding the Depth of the Subtree

  1. Initialize the depth calculation at the found node:

    • Once the node with value val is found, start calculating the depth of the subtree rooted at this node.
  2. Check if the current node is null:

    • If the current node is null, return 0 because a null node contributes no depth.
  3. Calculate the depth of the left subtree:

    • Recursively call the depth calculation method on the left child of the current node.
  4. Calculate the depth of the right subtree:

    • Recursively call the depth calculation method on the right child of the current node.
  5. Determine the maximum depth:

    • For the current node, calculate the depth as 1 + max(leftDepth, rightDepth) where leftDepth and rightDepth are the depths of the left and right subtrees, respectively.
  6. Return the calculated depth:

    • Return the depth calculated from the current node to its deepest leaf node, representing the depth of the subtree rooted at this node.

Algorithm Walkthrough

Input:

  • Root: [3, 5, 4, 2, null, 1, null, 6]
  • Val: 5

Step 1: Finding the Node with Value 5

  1. Start at the root node with value 3:

    • The current node is 3. The value 3 does not match val = 5.
    • Proceed to search in the left subtree of node 3.
  2. Move to the left child of node 3, which is 5:

    • The current node is now 5. The value 5 matches val = 5.
    • We have found the node where the subtree starts.
  3. Proceed to calculate the depth of the subtree rooted at node 5:

    • Now that the node with value 5 is found, we move on to calculating the depth of the subtree rooted at this node.

Step 2: Calculating the Depth of the Subtree Rooted at Node 5

  1. Calculate the depth of the left subtree of node 5:

    • Move to the left child of node 5, which is 2.
    • To find the depth of the subtree rooted at 2, proceed to its left child.
  2. Move to the left child of node 2, which is 6:

    • The current node is 6. It has no left or right children, meaning it's a leaf node.
    • The depth of node 6 is 1 because there are no further children.
  3. Calculate the depth of node 2:

    • Node 2 has a left depth of 1 (from node 6) and no right child.
    • The depth of node 2 is 1 + max(1, 0) = 2.
  4. Calculate the depth of the right subtree of node 5:

    • The right child of node 5 is null, so the right depth is 0.
  5. Determine the maximum depth of node 5:

    • Node 5 has a left depth of 2 (from node 2) and a right depth of 0.
    • The depth of node 5 is 1 + max(2, 0) = 3.
  6. Return the depth of the subtree rooted at node 5:

    • The final output is 3, which represents the depth of the subtree starting from the node with value 5.

Code

Java
Saved to Cloud

. . . .

Complexity Analysis

  • Time Complexity: The time complexity of the solution is , where N is the number of nodes in the binary tree. This is because we may need to traverse all nodes in the tree to find the node with value val and then calculate the depth of the subtree starting from that node.

  • Space Complexity: The space complexity is , where H is the height of the binary tree. This is due to the recursive depth-first search (DFS) approach, which will require stack space proportional to the height of the tree.

Find maximum depth of subtree (medium)
Introduction to Tree Breadth First Search Pattern
Mark as Completed

On this page

Problem Statement

Examples

Solution

Step-by-Step Algorithm

Algorithm Walkthrough

Code

Complexity Analysis